#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    void traverse(TreeNode *root, vector<int> &res)
    {
        if (root == nullptr)
        {
            return;
        }
        res.push_back(root->val);
        traverse(root->left, res);
        traverse(root->right, res);
    }
    vector<int> print_tree(TreeNode *root)
    {
        vector<int> res;
        traverse(root, res);
        return res;
    }
    // TreeNode *insertIntoBST(TreeNode *root, int val)
    // {
    //     if (root == nullptr)
    //     {
    //         return new TreeNode(val);
    //     }
    //     TreeNode *cur = root;
    //     TreeNode *pre = nullptr;
    //     int flag = 1;
    //     while (cur != nullptr)
    //     {
    //         if (val < cur->val)
    //         {
    //             pre = cur;
    //             cur = cur->left;
    //             flag = 1;
    //         }
    //         else if (val > cur->val)
    //         {
    //             pre = cur;
    //             cur = cur->right;
    //             flag = 2;
    //         }
    //     }
    //     cur = new TreeNode(val);
    //     if (flag == 1)
    //     {
    //         pre->left = cur;
    //     }
    //     else if (flag == 2)
    //     {
    //         pre->right = cur;
    //     }
    //     return root;
    // }

    // TreeNode *insertIntoBST(TreeNode *root, int val)
    // {
    //     if (root == nullptr)
    //     {
    //         TreeNode *cur = new TreeNode(val);
    //         return cur;
    //     }
    //     if (root->val > val)
    //     {
    //         root->left = insertIntoBST(root->left, val);
    //     }
    //     if (root->val < val)
    //     {
    //         root->right = insertIntoBST(root->right, val);
    //     }
    //     return root;
    // }

    void recursion(TreeNode *cur, int val)
    {
        if (cur == nullptr)
        {
            if (val > pre->val)
            {
                pre->right = new TreeNode(val);
            }
            else
            {
                pre->left = new TreeNode(val);
            }
            return;
        }
        pre = cur;
        if (val > cur->val)
        {
            recursion(cur->right, val);
        }
        else
        {
            recursion(cur->left, val);
        }
    }
    TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        if (root == nullptr)
        {
            return new TreeNode(val);
        }
        recursion(root, val);
        return root;
    }
    TreeNode *pre = nullptr;
};

int main()
{
    TreeNode *root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    Solution sol;
    TreeNode *res = sol.insertIntoBST(root, 5);
    vector<int> vec = sol.print_tree(res);
    for (auto const num : vec)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}